/**
 * WTF Engine
 *
 * License... etc.
 **
 * Work API
 * @file src/work.h
 *
 * Abstracts the notion of parallel processing, through
 * work items and workers, each of which meet in the work
 * pool. Work items are dispatched to workers by the controller,
 * a special worker which represents the main thread of execution
 * in the program. Workers can also obtain work themselves through
 * work stealing.
 *
 * The Work API is designed to be as general as possible, allowing
 * the engine to easily harness next-gen technologies such as many-core,
 * general-purpose GPUs, and the Cell architecture.
 **
 * Author: Sean Micklethwaite
 **/

#ifndef __workH__
#define __workH__

#include "mm.h"

namespace WtfEngine {
	template <class T>
	class SafeList;

	/**
	 * Base class for safe list elements.
	 **/
	template <class T>
	class SafeListBase
	{
		protected:
			T* mpListPtr;

		public:
			SafeListBase() : mpListPtr(NULL) {};

			friend class SafeList<T>;
	};


	class WorkItem: public GcObject, public SafeListBase<WorkItem> {
		bool mbEvaluated;

		public:
			WorkItem(): GcObject(), SafeListBase<WorkItem>(), mbEvaluated(false) {};

			/// Adds the item to the work pool, so it can be evaluated by
			/// other workers.
			void Create();

			/// @warning
			/// By specification, work items must be evaluated before they can be deleted.
			/// Unfortunately, destructor ordering may mean that data local to a derived
			/// class of WorkItem is lost by the time this destructor is called. In that case,
			/// the destructor of the derived class should call Sync() itself.
			virtual ~WorkItem(){
				Sync();
			}

			/// This operator represents the actual
			/// computation.
			virtual void operator()(void)=0;

			/**
			 * Evaluate:
			 * Performs the computation.
			 *
			 * Specification:
			 * @pre	!Evaluated && �(F memberof WorkList)
			 * @post Evaluated
			 **/
			void Evaluate()
			{
				if(mbEvaluated) return;
				(*this)();
				mbEvaluated = true;
			};

			/// Waits until the work item is evaluated, can only
			/// be invoked by the controller.
			void Sync();
			
			bool isEvaluated() const {
				return mbEvaluated;
			};
	};


	class Worker: public GcObject, public SafeListBase<Worker> {
		public:
			Worker(): GcObject(), SafeListBase<Worker>() {};

			virtual bool Accepts(const WorkItem::tRef& rWorkItem) = 0;
	};


	/**
	 * Thread-safe lockless unordered list class. Implements
	 * a multiset.
	 *
	 * ABSTRACT:
	 * 	l : SafeListBase T => multiset T
	 **/
	template <class T>
	class SafeList
	{
		private:
			T*	mpListHead;

			static bool SetPtr(T*& p, T* pOld, T* pNew){
	#ifdef _MSC_VER
				__asm { // TODO: not portable!!
					mov eax, pOld;
					mov ebx, pNew;
					mov edx, p;
					lock cmpxchg dword ptr [edx], ebx;
				}
	#elif __GNUC__
				__asm volatile(
							   "lock cmpxchg %%ebx,(%%edx);"
					::"a"(pOld),"b"(pNew),"d"(p));
	#else
	#	error Unsupported compiler
	#endif
				return (p == pNew);
			}

		public:
			SafeList() : mpListHead(NULL) {};

			/**
			 * Insert: safely inserts item p into the list.
			 *
			 * Specification:
			 * PRE:
			 * POS: p memberof List
			 */
			void Insert(T* p)
			{
				do{
					p->mpListPtr = mpListHead;
				}while(!SetPtr(mpListHead, p->mpListPtr, p));
			}

			/**
			 * Remove: removes the first instance of p from the list.
			 *
			 * Specification:
			 * PRE:
			 * POS: p memberof List0 => (|p in List| = |p in List0| - 1)
			 */
			void Remove(T* p)
			{
				T ** pp; T* pNext;
				bool bSuccess;
				do{
					bSuccess = true;
					for(pp = &mpListHead; (pNext = *pp) != NULL; pp = &(pNext->mpListPtr)){
						if(*pp == p){
							bSuccess = SetPtr(*pp, p, p->mpListPtr);
							break;
						};
					};
				}while(!bSuccess);
			};

			/**
			 * Pop: removes the first element in the the list, and returns it.
			 *
			 * Specification:
			 * PRE:
			 * POS: |List0| > 1 => (List[0..] = List0[1..]
			 *			^ r = List0[0])
			 *		List0 = [] => r = NULL
			 */
			T* Pop()
			{
				T* p;
				do{
					p = mpListHead;
					if(p == NULL) break;
				}while(!SetPtr(mpListHead, p, p->mpListPtr));
				return p;
			}

			bool IsEmpty() const{
				return (mpListHead == NULL);
			}
	};


	/**
	 * The work pool manages all the available workers in the system, and
	 * allocates & dispatches work items to them.
	 *
	 * The notion of work items and workers are heavily generalised, and can
	 * be anything from a pool of threads matching the number of cores in a
	 * system, to a worker representing a GPU that can accept shader work. In
	 * the latter case, the work item must provide a shader program, which is
	 * why workers have an 'Accepts' method, to determine whether a particular
	 * work item is acceptable for the worker.
	 **/
	class WorkPool: public Singleton<WorkPool> {

		/// Non-thread safe list of all workers, kept for administrative
		/// purposes.
		std::list<Worker::tRef>	mWorkers;

		/// List of available workers, workers add themselves to this before
		/// sleeping. Work can be dispatched to an available worker directly.
		SafeList<Worker>		mAvailableWorkers;

		/// List of outstanding work to be done, is read by workers.
		SafeList<WorkItem>		mWorkList;

		public:
			WorkPool(int n = -1);

			/// Returns true if the current thread is the controller.
			bool IsController();

		protected:
			/// Adds a work item to the work list, resulting in eventual
			/// dispatch to a worker.
			/// TODO: check for available workers.
			void AddWorkItem(WorkItem* p){
				mWorkList.Insert(p);
			};



			friend class WorkItem;
			friend class Worker;
	};
};

#endif
